package Leetcode;

/* 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/

class Solution1{  //动态规划
	public int uniquePaths(int m,int n) {  //设定一个二维数组，m为高，n为宽
		int [][] num = new int [m][n];
		for(int i = 0;i<n;i++) {	//将边界都设为1，因为边界就一条路
			num[0][i] = 1;
		}
		for(int i=1;i<m;i++) {	
			num[i][0] = 1;
		}
		for(int i=1;i<m;i++) {	//因为只能向下或向右移动，所以边界内将上和左的元素相加即为到该格的不同方法
			for(int j=1;j<n;j++) {
				num[i][j] = num[i-1][j]+num[i][j-1];
			}
		}
		return num[m-1][n-1];
	}
}

class Solution2 {	//公式法
    public int uniquePaths(int m, int n) {
        long ans = 1;
        for (int x = n, y = 1; y < m; ++x, ++y) {
            ans = ans * x / y;
        }
        return (int) ans;
    }
}

public class leetcode62 {
	public static void main(String [] args) {
		
	}
}
